package JavaCode.contest.weekly.n201_300.n235;

import utils.Parse;

import java.util.*;

/**
 * author: fangjie
 * email: syfangjie@live.cn
 * date: 2021/4/4 10:29 上午
 */
public class N4 {
    public static void main(String[] args) {
        System.out.println(new N4().countDifferentSubsequenceGCDs(
                Parse.toIntArr("[19,3,9]")
        ));
    }

    private final static int MAX=2*100000+1;
    private final static List<Integer>[] factors=new List[MAX];
    private final static int[] book=new int[MAX];
    static{
        //预计算
        for (int i=1;i<MAX;i++)factors[i]=new ArrayList<>();
        for (int i=1;i<MAX;i++){
            for (int j=i;j<MAX;j+=i){
                factors[j].add(i);
            }
        }
    }

    public int countDifferentSubsequenceGCDs(int[] nums) {
        int max=0;
        for (int i:nums)max=Math.max(max,i);
        Arrays.fill(book,0);
        for (int num:nums){
            for (int factor:factors[num]){
                book[factor]++;
            }
        }

        int res=0;
        for (int i=max;i>=1;i--){
            if(book[i]==0)continue;
            boolean flag=true;
            for (int j=i*2;j<=max;j+=i){
                if(book[i]==book[j]){
                    flag=false;
                    break;
                }
            }
            if(flag)res++;
        }
        return res;

    }

}
/*
给你一个由正整数组成的数组 nums 。

数字序列的 最大公约数 定义为序列中所有整数的共有约数中的最大整数。

例如，序列 [4,6,16] 的最大公约数是 2 。
数组的一个 子序列 本质是一个序列，可以通过删除数组中的某些元素（或者不删除）得到。

例如，[2,5,10] 是 [1,2,1,2,4,1,5,10] 的一个子序列。
计算并返回 nums 的所有 非空 子序列中 不同 最大公约数的 数目 。



示例 1：


输入：nums = [6,10,3]
输出：5
解释：上图显示了所有的非空子序列与各自的最大公约数。
不同的最大公约数为 6 、10 、3 、2 和 1 。
示例 2：

输入：nums = [5,15,40,5,6]
输出：7


提示：

1 <= nums.length <= 105
1 <= nums[i] <= 2 * 105
 */
